package com.lw.leetcode.tree.c;

/**
 * Created with IntelliJ IDEA.
 * c
 * tree
 * 2509. 查询树中环的长度
 *
 * @author liw
 * @version 1.0
 * @date 2022/12/19 14:12
 */
public class CycleLengthQueries {

    public int[] cycleLengthQueries(int n, int[][] queries) {
        int length = queries.length;
        int[] arr = new int[length];
        int[] items1 = new int[32];
        int[] items2 = new int[32];
        int l1 = 0;
        int l2 = 0;
        for (int i = 0; i < length; i++) {
            int[] query = queries[i];
            l1 = find(query[0], items1);
            l2 = find(query[1], items2);
           arr[i] = count(items1, items2, l1, l2);
        }
        return arr;
    }

    private int find(int n, int[] arr) {
        int index = 0;
        while (n != 1) {
            arr[index++] = n;
            n >>= 1;
        }
        arr[index++] = n;
        return index - 1;
    }

    private int count(int[] items1, int[] items2, int l1, int l2) {
        while (l1>= 0&& l2 >= 0) {
            if (items1[l1] == items2[l2]) {
                l1--;
                l2--;
            } else {
                break;
            }
        }
        return l1 + l2 + 3;
    }

}
